package 单调队列;

import java.util.Deque;
import java.util.LinkedList;

//183 望远镜中最高海拔（滑动窗口最大值）
//注：此题还可以利用优先级队列，但是时间复杂度就不是on了，是nlogn
public class Solution1 {
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights==null||limit==0){
            return new int[0];
        }
        int[] res = new int[heights.length-limit+1];
        int j =0;
        Deque<Integer> queue = new LinkedList<>();
        for(int i=0;i<heights.length;i++){
            if(!queue.isEmpty()&&queue.getFirst()<i-limit+1) queue.pollFirst();
            while(!queue.isEmpty()&&heights[i]>heights[queue.getLast()]){
                queue.pollLast();
            }
            queue.addLast(i);
            if(i>=limit-1){
                res[j++]=heights[queue.getFirst()];
            }
        }
        return res;
    }
}
